package leetcode.list;

/**
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 */
public class LeetCode25_ReverseKGroup {
    public ListNode reverseKGroup(ListNode head, int k) {

        if(k < 2) {
            return head;
        }

        // 链表长度
        int n = 0;
        ListNode th = head;
        while (th != null) {
            th = th.next;
            n++;
        }
        // 链表长度不足k
        if (n < k) {
            return head;
        }

        // 需要反转的 组数
        int reverseGroupCount = n / k;
        // 新的头节点在第一组中
        ListNode newHead = null;
        // 反转group链表参数
        ListNode pre, cur = null, next;
        // 当前组的
        ListNode groupNext = head;
        // 前一组反转后的尾节点
        ListNode preGroupHead = head;
        // 当前组未反转前的头节点
        ListNode groupHead;
        int tempK = 0;
        while (reverseGroupCount > 0) {
            pre = null;
            cur = groupNext;
            groupHead = cur;
            // group内反转
            while (tempK < k) {

                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;

                tempK++;
            }

            // 第一组反转后的头节点
            if (reverseGroupCount == n / k) {
                newHead = pre;
            }else {
                // 反转后组的尾节点指向下一组反转后的头节点
                preGroupHead.next = pre;
                preGroupHead = groupHead;
            }

            // 下一组的开始节点
            groupNext = cur;

            tempK = 0;
            reverseGroupCount--;
        }
        // 不足k的组
        preGroupHead.next = cur;

        return newHead;
    }

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode a2 = new ListNode(2);
        a.next = a2;
        ListNode a3 = new ListNode(3);
        a2.next = a3;
        ListNode a4 = new ListNode(4);
        a3.next = a4;
        ListNode a5 = new ListNode(5);
        a4.next = a5;

//        ListNode listNode = new LeetCode25_ReverseKGroup().reverseKGroup(a, 2);
        ListNode listNode = new LeetCode25_ReverseKGroup().reverseKGroup(a, 3);
        System.out.println("listNode = " + listNode);

    }
}
